#include <bits/stdc++.h>
using namespace std;

/*
1751. 最多可以参加的会议数目 II
已解答
困难
相关标签
premium lock icon
相关企业
提示
给你一个 events 数组，其中 events[i] = [startDayi, endDayi, valuei] ，表示第 i 个会议在 startDayi 天开始，第 endDayi 天结束，如果你参加这个会议，你能得到价值 valuei 。同时给你一个整数 k 表示你能参加的最多会议数目。

你同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须 完整 地参加完这个会议。会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。

请你返回能得到的会议价值 最大和 。

 

示例 1：



输入：events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
输出：7
解释：选择绿色的活动会议 0 和 1，得到总价值和为 4 + 3 = 7 。
示例 2：



输入：events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
输出：10
解释：参加会议 2 ，得到价值和为 10 。
你没法再参加别的会议了，因为跟会议 2 有重叠。你 不 需要参加满 k 个会议。
示例 3：



输入：events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
输出：9
解释：尽管会议互不重叠，你只能参加 3 个会议，所以选择价值最大的 3 个会议。
 

提示：

1 <= k <= events.length
1 <= k * events.length <= 106
1 <= startDayi <= endDayi <= 109
1 <= valuei <= 106
*/


// 法一
class Solution {
public:
    int maxValue(vector<vector<int>>& events, int k) {
        int n = events.size();
        sort(events.begin(), events.end(),
             [](const vector<int>& a, const vector<int>& b) {
                 return a[1] < b[1];
             });
        // dp 来表示前i个中选择j个会议的最大值
        // 没有会议或者不选会议的时候初始化为0
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));

        // 迭代
        for (int i = 1; i <= n; i++) {
            int start = events[i - 1][0];
            int end = events[i - 1][1];
            int val = events[i - 1][2];

            // 二分 找到最后一个不与当前重叠的
            // == max（p） 满足 events[p].end < start
            int left = 0, right = i - 1;
            int pos = 0;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (events[mid][1] < start) {
                    pos = mid + 1; // p是第一个不满足条件的，因此mid+1可能是解
                    left = mid + 1;
                } else
                    right = mid - 1;
            }
            // 状态转移 选择j个会议的情况
            // 1. 不选当前会议：继承dp[i-1][j]
            // 2. 选当前会议：dp[p][j-1] +
            // value（需要确保前p个会议不与当前会议重叠）
            for (int j = 1; j <= k; ++j) {
                dp[i][j] = max(dp[i-1][j], dp[pos][j-1] + val);
            }      
        }
        return dp[n][k];
    }
};

// 法二
class Solution {
public:
    int maxValue(vector<vector<int>> &events, int k) {
        // 1. 按会议结束时间升序排序，方便后续处理不重叠的会议
        sort(events.begin(), events.end(), [](auto &a, auto &b) { 
            return a[1] < b[1]; 
        });

        int n = events.size();
        // 2. 定义动态规划数组：f[i][j]表示前i个会议选j个时的最大价值
        int f[n + 1][k + 1];
        memset(f, 0, sizeof(f)); // 初始化为0（不选任何会议时价值为0）

        for (int i = 0; i < n; ++i) {
            // 3. 二分查找：找到最后一个结束时间 < 当前会议开始时间的会议p
            //    即events[p].end < events[i].start，且events[p+1].end >= events[i].start
            int p = lower_bound(events.begin(), events.begin() + i, events[i][0],
                                [](auto &e, int lower) { 
                                    return e[1] < lower; // 比较结束时间与当前会议开始时间
                                }) - events.begin();

            for (int j = 1; j <= k; ++j) {
                // 4. 状态转移：
                //    - 不选当前会议：继承f[i][j]
                //    - 选当前会议：f[p][j-1] + value（需确保前p个会议不与当前会议重叠）
                //    注意：p的计算已保证events[p].end < events[i].start，因此直接使用p而非p+1
                f[i + 1][j] = max(f[i][j], f[p][j - 1] + events[i][2]);
            }
        }
        // 5. 返回前n个会议选k个的最大价值
        return f[n][k];
    }
};